package com.sh.sort;

import java.util.Arrays;

/**
 * @ClassName QuickSort
 * @Description TODO
 * @Author yaoqiang
 * @Date 2020/11/8 18:21
 * @Version 1.0
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr={-9,78,0,23,-567,70};
        quickSort(arr,0,arr.length-1);
        Arrays.toString(arr);
    }
    public static void quickSort(int[] arr,int left,int right){
        int leftIndex=left;//做下标
        int rightIndex=right;//由下标
        int pivot=arr[(left+right)/2];//中轴值
        int temp =0;
        //while循环的目标是左边的比中间值小，右边的比pivot大
        while (leftIndex<rightIndex){
            //从左边找到一个大于中间值的才推出
            while (arr[leftIndex]<pivot){
                leftIndex+=1;
            }
            while (arr[rightIndex]>pivot){
                rightIndex-=1;
            }
            if (leftIndex>=rightIndex){
                break;
            }
            //交换
            temp=arr[leftIndex];
            arr[leftIndex]=arr[rightIndex];
            arr[rightIndex]=temp;
            //如果交换完，发现arr[leftIndex]==pivot相等
            if (arr[leftIndex]==pivot){
                rightIndex-=1;

            }
            if (leftIndex==rightIndex){
                leftIndex+=1;

            }
            if (left<rightIndex){
                quickSort(arr,left,rightIndex);
            }

            if (right>1){
                quickSort(arr,leftIndex,right);
            }

        }

    }

}
